package top.lcm668.study.oj.base.sortmethods.mergesort;

/**
 * @author: Coder-Lcm
 * @date: 2021/10/5 8:30
 * 自底向上的归并排序算法: 先归并那些微型数组，然后成对归并得到的微型数组。
 */
public class Down2UpMergeSort<T extends Comparable<T>> extends BaseMergeSort<T> {

    @Override
    protected void sort(T[] arr, boolean isAsc) {
        int len = arr.length;
        helperArr = (T[]) new Comparable[arr.length];
        for (int i = 1; i < len; i += i) {
            for (int i1 = 0; i1 < len - i; i1 += i + i) {
                merge(arr, i1, i1 + i - 1, Math.min(i1 + i + i - 1, len - 1));
            }
        }
    }
}
